#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 455:Assign Cookies
// 先尝试满足最不贪心小朋友:最大饼干给最贪心小朋友
// O(nlogn)  O(1)
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
		sort(g.begin(), g.end());	// 从小到大
		sort(s.begin(), s.end());
		
		int gi = 0, si = 0;		// 代表索引 分别指向最贪心小朋友 和 最大饼干
		int res = 0;
		while(gi < g.size() && si < s.size()){
			if(s[si] >= g[gi]){		// 当前能拿到最大饼干 能满足 最贪心小朋友
				res++;				// 满足的小朋友数
				si++;
				gi++;
			}else{
				si++;		// 饼干变大
			}
		}
		return res;
    }
};

int main(){
	int g1[] = {1, 2, 3};
    vector<int> gv1(g1, g1 + sizeof(g1)/sizeof(int));
    int s1[] = {1, 1};
    vector<int> sv1(s1, s1 + sizeof(s1)/sizeof(int));
    cout << Solution().findContentChildren(gv1, sv1) << endl;

    int g2[] = {1, 2};
    vector<int> gv2(g2, g2 + sizeof(g2)/sizeof(int));
    int s2[] = {1, 2, 3};
    vector<int> sv2(s2, s2 + sizeof(s2)/sizeof(int));
    cout << Solution().findContentChildren(gv2, sv2) << endl;

    return 0;	
}
